package codingInterview.leetcode.editor.cn;

//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 
//
// 
//
// 示例 1: 
//
// 输入: [7,5,6,4]
//输出: 5 
//
// 
//
// 限制： 
//
// 0 <= 数组长度 <= 50000 
// Related Topics 树状数组 线段树 数组 二分查找 分治 有序集合 归并排序 👍 666 👎 0

import java.util.Arrays;

//Java：剑指 Offer 51 - 数组中的逆序对
public class ShuZuZhongDeNiXuDuiLcof{
    public static void main(String[] args) {
                Solution solution = new ShuZuZhongDeNiXuDuiLcof().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int[] nums,tmp;
    public int reversePairs(int[] nums) {
        if(nums.length <=1) return 0;
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length-1);
    }
    public int mergeSort( int left, int right){
        if(left>=right) return 0; // 终止条件
        int middle = (left+right)/2;
        int count = mergeSort(left, middle) + mergeSort(middle+1, right);

        int i=left,j=middle+1;
        for (int k = left; k <= right; k++) {
            tmp[k] = nums[k]; // 临时保存
        }
        for (int k = left; k <= right; k++) {
            if(i== middle+1){ // 左边走完了
                nums[k] = tmp[j++]; // 存好排序后的
            }else if(j==right+1 || tmp[i]<=tmp[j]){ // 右边走完或者没有逆序
                nums[k] = tmp[i++]; // 存好排序后的
            }else{  // 存在逆序 tmp[i]>tmp[j]
                nums[k] = tmp[j++]; // 存好排序后的
                count+=middle-i+1; // 计数存在的逆序对,此时 [i-middle] 均大于 j
            }
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
